package com.wsx.first.a;

import java.util.Scanner;

/**
 * @author: wangshunxi
 * @date: 2022/5/6 10:45
 * @Description:
 */
public class Main0004 {
/*
一天一只顽猴想要从山脚爬到山顶
途中经过一个有n个台阶的阶梯，但是这个猴子有个习惯，每一次只跳1步或3步
试问？猴子通过这个阶梯有多少种不同的跳跃方式
输入只有一个这个数n 0 < n < 50
此阶梯有多个台阶
 **/

    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            //10
            int n = scanner.nextInt();
            //28
            solution(n);
            solution2(n);
            solution3(n);
        }
    }

    private static void solution(int n) {
        int step1 = 1, step2 = 1, step3 = 2;
        int step4 = n == 1 || n == 2 ? 1 : 2;
        for (int i = 4; i <= n; i++) {
            step4 = step3 + step1;
            step1 = step2;
            step2 = step3;
            step3 = step4;
        }
        System.out.println(step4);
    }

    private static void solution2(int n) {
        System.out.println(coreSolution(n));
    }

    private static void solution3(int n) {
        System.out.println(coreSolution3(n));
    }

    private static int coreSolution(int n) {
        //归纳 由简单到复杂
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        return coreSolution(n - 1) + coreSolution(n - 3);
    }

    private static int coreSolution3(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        int[] result = new int[n+1];
        //初始化
        result[1] = 1;
        result[2] = 1;
        result[3] = 2;
        for (int i = 4; i <= n; i++) {
            result[i] = result[i - 1] + result[i - 3];
        }
        return result[n];
    }

}
